package com.leetcode.partition3;

import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/7/29 9:10
 */
public class LC215数组中第K个最大元素 {

    public static int findKthLargest(int[] nums, int k) {
        return heap(nums, k);
    }

    public static int heap(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.add(num);
            if (heap.size() > k) heap.poll();
        }
        return heap.peek();
    }

    public static int method1(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }

    public static void quickSort(int[] arr, int i, int j) {
        int li = i, lj = j;
        int pivot = arr[i];
        while (li < lj) {
            while (li < lj && pivot <= arr[lj]) lj--;
            if (li < lj) arr[li++] = arr[lj];

            while (li < lj && arr[li] < pivot) li++;
            if (li < lj) arr[lj--] = arr[li];

            arr[li] = pivot;
        }
        if (i < li) quickSort(arr, i, li - 1);
        if (li < j) quickSort(arr, lj + 1, j);
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5, 6, 4};
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(5);
        queue.add(4);
        queue.add(3);
        queue.add(2);
        queue.add(1);
        System.out.println(queue);
        queue.poll();
        System.out.println(queue);
    }
}
